Knowledge Accumulator

Covariance matrix adaptation evolution strategy - пример того, как делать ресёрч для людей, а не начальства

Две недели назад я говорил про базовый алгоритм из семейства Evolution Strategies. Сегодня мы посмотрим на CMA-ES - его улучшенную версию.

Область применения всё ещё та же - у нас есть пространство параметров и функция качества, которую мы хотим оптимизировать. Доступа к производным нет.

Базовый алгоритм сэмплировал нормальные шумы с фиксированной дисперсией и накладывал их на текущее значение параметров, получая новые точки, в которых оценивалась награда и с помощью которых вычислялась оценка градиента по параметрам в текущей точке.

CMA-ES двигается дальше. Он переходит от фиксированной дисперсии нормального шума к полноценной матрице ковариаций, вводя в алгоритм межпараметрное взаимодействие.

После того, как мы засэмплировали N шумов и посчитали качество итоговых точек, мы пересчитываем матрицу ковариации нормального шума таким образом, чтобы максимизировать вероятность выпадения тех шумов, которые привели к более высоким наградам.

Таким образом, мы "обучаем" направление эволюционного поиска. Автор утверждает, что это можно интерпретировать как Natural Gradient Descent - метод оптимизации второго порядка.

Второе улучшение, вводимое в алгоритм, заключается в использовании некоторого рода "моментов", называемых тут Evolution Paths. Очевидно, если мы много итераций подряд двигаем какой-то параметр в одну и ту же сторону, это значит, что нам можно начать двигаться быстрее в эту сторону.

Алгоритм математически нагруженный. Полностью разобраться в его устройстве за короткое время, в отличие от базового ES, не представляется возможным. Именно в таких обстоятельствах автор алгоритма - Nikolaus Hansen - поворачивается к человечеству лицом.

Он мог бы опубликовать свою статью на глубоко уважаемой научной конференции, получить премию и забить хер, но вместо этого предоставил людям все инструменты для того, чтобы результаты его труда можно было использовать.

У алгоритма есть читаемая статья на вики, статья-туториал, страница с практическими подсказками и ссылками на реализации алгоритма на 8 языках, в том числе живой питон-репозиторий с кучей документации и элементарными примерами использования.

Несмотря на очень сложный алгоритм, автор сделал всё, чтобы даже такая обезьяна, как я, смогла без каких-либо проблем использовать его для решения своей задачи.

Я не знаю, каким образом и почему спустя почти 30 лет после изобретения алгоритма автор продолжает всем этим заниматься. Испытываю глубочайшее уважение к такому подходу к ресёрчу, в отличие от современного "высрал и забыл".

У CMA-ES ещё к 2009-му накопился список из более чем сотни применений. Данный алгоритм и сегодня используется как один из бейзлайнов в своей области применения, хоть и не является SOTA. Учитесь, салаги.

@knowledge_accumulator

www.tg-me.com/ua/Knowledge Accumulator/com.knowledge_accumulator/263

3.1K viewsFeb 25 at 11:32

Covariance matrix adaptation evolution strategy - пример того, как делать ресёрч для людей, а не начальства

Две недели назад я говорил про базовый алгоритм из семейства Evolution Strategies. Сегодня мы посмотрим на CMA-ES - его улучшенную версию.

Область применения всё ещё та же - у нас есть пространство параметров и функция качества, которую мы хотим оптимизировать. Доступа к производным нет.

Базовый алгоритм сэмплировал нормальные шумы с фиксированной дисперсией и накладывал их на текущее значение параметров, получая новые точки, в которых оценивалась награда и с помощью которых вычислялась оценка градиента по параметрам в текущей точке.

CMA-ES двигается дальше. Он переходит от фиксированной дисперсии нормального шума к полноценной матрице ковариаций, вводя в алгоритм межпараметрное взаимодействие.

После того, как мы засэмплировали N шумов и посчитали качество итоговых точек, мы пересчитываем матрицу ковариации нормального шума таким образом, чтобы максимизировать вероятность выпадения тех шумов, которые привели к более высоким наградам.

Таким образом, мы "обучаем" направление эволюционного поиска. Автор утверждает, что это можно интерпретировать как Natural Gradient Descent - метод оптимизации второго порядка.

Второе улучшение, вводимое в алгоритм, заключается в использовании некоторого рода "моментов", называемых тут Evolution Paths. Очевидно, если мы много итераций подряд двигаем какой-то параметр в одну и ту же сторону, это значит, что нам можно начать двигаться быстрее в эту сторону.

Алгоритм математически нагруженный. Полностью разобраться в его устройстве за короткое время, в отличие от базового ES, не представляется возможным. Именно в таких обстоятельствах автор алгоритма - Nikolaus Hansen - поворачивается к человечеству лицом.

Он мог бы опубликовать свою статью на глубоко уважаемой научной конференции, получить премию и забить хер, но вместо этого предоставил людям все инструменты для того, чтобы результаты его труда можно было использовать.

У алгоритма есть читаемая статья на вики, статья-туториал, страница с практическими подсказками и ссылками на реализации алгоритма на 8 языках, в том числе живой питон-репозиторий с кучей документации и элементарными примерами использования.

Несмотря на очень сложный алгоритм, автор сделал всё, чтобы даже такая обезьяна, как я, смогла без каких-либо проблем использовать его для решения своей задачи.

Я не знаю, каким образом и почему спустя почти 30 лет после изобретения алгоритма автор продолжает всем этим заниматься. Испытываю глубочайшее уважение к такому подходу к ресёрчу, в отличие от современного "высрал и забыл".

У CMA-ES ещё к 2009-му накопился список из более чем сотни применений. Данный алгоритм и сегодня используется как один из бейзлайнов в своей области применения, хоть и не является SOTA. Учитесь, салаги.

@knowledge_accumulator

BY Knowledge Accumulator